package Heap;

import java.util.PriorityQueue;

public class _857_MinimumCosttoHireKWorkers {
    public double mincostToHireWorkers(int[] quality, int[] wage, int K) {
        double totalWage = Integer.MAX_VALUE;
        int len = quality.length;
        for (int i = 0; i < len; i++) {
            PriorityQueue<double[]> p = new PriorityQueue<double[]>((info1, info2) -> info1[0] - info2[0] < 0 ? -1 : 1);
            for (int j = 0; j < len; j++) {
                p.offer(new double[]{(double) quality[j] / (double) quality[i] * (double) wage[i], quality[j], j});
            }
            double tempWage = 0;
            int restHire = K;
            while (!p.isEmpty() && restHire > 0) {
                double[] offer = p.poll();
                if (offer[0] >= wage[(int) offer[2]]) {
                    if (restHire == K && ((int) offer[1]) >= K) {
                        restHire -= K - 1;
                        tempWage += (K - 1) * offer[0];
                    } else {
                        int hire = (int) offer[1] > restHire ? restHire : (int) offer[1];
                        restHire -= hire;
                        tempWage += (hire) * offer[0];
                    }
                }
            }
            if (restHire == 0) {
                totalWage = Math.min(totalWage, tempWage);
            }
        }
        return totalWage;
    }

}
